package algorithm.CBTCount;

/*
求完全二叉树节点的个数，要求时间复杂度为O((logN)^2)
 */
public class CBTCount {
    static class Node {
        Node left;
        Node right;

        public Node() {
        }
    }

    public static int high;

    public static int getCount(Node node) {
        if (node == null)
            return 0;
        //遍历左子树求高度
        Node root = node;
        int curHigh = 0;
        while (node.left != null) {
            curHigh++;
            node = node.left;
        }

        //求右子树高度
        if (root.right == null) {
            if (root.left == null)
                return 1;
            return 2;
        }
        node = root.right;
        int lcHigh = 1;
        while (node.left != null) {
            lcHigh++;
            node = node.left;
        }

        if (lcHigh == curHigh) {  //根的左子树是满树
            return (int) Math.pow(2, curHigh) - 1 + 1 + getCount(root.right);
        } else {
            return getCount(root.left) + 1 + (int) Math.pow(2, lcHigh) - 1;
        }
    }

    public static void main(String[] args) {
        Node node = new Node();

        node.left = new Node();
        node.right = new Node();

        node.left.left = new Node();
        node.left.right = new Node();
        node.right.left = new Node();
        node.right.right = new Node();

        node.left.left.left = new Node();
        node.left.left.right = new Node();
        node.left.right.left = new Node();
        node.left.right.right = new Node();
        node.right.left.left = new Node();
        node.right.left.right = new Node();
        node.right.right.left = new Node();
        node.right.right.right = new Node();

        node.left.left.left.left = new Node();
        node.left.left.left.right = new Node();
        node.left.left.right.left = new Node();
        node.left.right.left.left = new Node();
        node.left.right.right.left = new Node();
        node.right.left.left.left = new Node();
        node.right.left.right.left = new Node();
        node.right.right.left.left = new Node();
        node.right.right.right.left = new Node();
        node.left.left.right.right = new Node();
        node.left.right.left.right = new Node();
        node.left.right.right.right = new Node();
        node.right.left.left.right = new Node();
        node.right.left.right.right = new Node();
        node.right.right.left.right = new Node();
        node.right.right.right.right = new Node();

        node.left.left.left.left.left = new Node();
        node.left.left.left.left.right = new Node();

        System.out.println(getCount(node));
    }
}
